Algoritmo FFT (Fast Fourier Transform)

El algoritmo FFT (por sus siglas en inglés, Fast Fourier Transform) es un método eficiente para calcular la Transformada Discreta de Fourier (DFT) de una señal. En términos simples, permite convertir una señal del dominio del tiempo al dominio de la frecuencia.

Intuición

Imaginá que tenés una señal de audio, una serie de precios, o cualquier secuencia de valores que varía en el tiempo. La FFT te dice qué frecuencias (componentes senoidales) están presentes dentro de esa señal y con qué intensidad.

• Si aplicás una FFT a una canción, podés ver qué notas (frecuencias) suenan.
• Si la aplicás a una serie de precios financieros, podés detectar ciclos o patrones repetitivos.

Qué hace matemáticamente

La Transformada Discreta de Fourier (DFT) convierte una secuencia \( x[n] \) (en el tiempo) en una secuencia \( X[k] \) (en frecuencia):

\[ X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j 2 \pi k n / N} \]

Calcular esto directamente cuesta \( O(N^2) \) operaciones, lo cual es ineficiente para señales grandes. El algoritmo FFT reduce esa complejidad a \( O(N \log N) \) aprovechando la simetría y periodicidad de los números complejos, permitiendo así procesar señales en tiempo real.

Ejemplo práctico en Python

        import numpy as np
        import matplotlib.pyplot as plt

        # Crear una señal con dos frecuencias
        fs = 1000  # frecuencia de muestreo (Hz)
        t = np.linspace(0, 1, fs)
        signal = np.sin(2*np.pi*50*t) + 0.5*np.sin(2*np.pi*120*t)

        # Aplicar FFT
        fft_result = np.fft.fft(signal)
        frequencies = np.fft.fftfreq(len(signal), 1/fs)

        # Mostrar espectro
        plt.plot(frequencies[:fs//2], np.abs(fft_result)[:fs//2])
        plt.title("Espectro de frecuencias")
        plt.xlabel("Frecuencia (Hz)")
        plt.ylabel("Amplitud")
        plt.show()
      

El resultado mostrará picos en 50 Hz y 120 Hz, las frecuencias presentes en la señal.

Usos comunes

• Procesamiento de audio y música 🎵
• Análisis de vibraciones o fallas mecánicas 🔧
• Procesamiento de imágenes 📸
• Telecomunicaciones (modulación/demodulación) 📡
• Análisis de datos financieros para detectar ciclos 📈

En resumen, la FFT es una herramienta fundamental para cualquier área donde se analicen señales, ya que permite ver la estructura oculta en el dominio de las frecuencias.